/**
* Binomial.as - Generate Binomial coefficients, either individually or as a single row in Pascal's triangle
*
* Copyright (c) 2007, Jim Armstrong.  All rights reserved.
*
* This software program is supplied 'as is' without any warranty, express, 
* implied, or otherwise, including without limitation all warranties of 
* merchantability or fitness for a particular purpose.  Jim Armstrong shall not 
* be liable for any special incidental, or consequential damages, including, 
* witout limitation, lost revenues, lost profits, or loss of prospective 
* economic advantage, resulting from the use or misuse of this software program.
*
* @author Jim Armstrong, Singularity (www.algorithmist.net)
*
* @version 1.0
*/
package singularity.numeric;

  class Binomial
   {
    // core
    
    // core
    var __row:Array<Int>;                // currently generated row (nonsymmetric portion)
    var __n:Int;                 // row Float or 'n' in binomial coefficient (n k)
  
    public function new()
    {
      __n   = 2;
      __row = [1,2];
    }

/**
* @description coef( _n:Int, _k:Int ) - Generate the binomial coefficient (n k)
*
* @param _n:Int - n items
* @param _k:Numer  - k at a time
*
* @since 1.0
*
* @return Float:Binomial coefficient (n k)
*
*/
    public function coef( _n:Int, _k:Int ):Int   
    {
      if( _k > _n )
        return 0;
      else if( _k == _n )
        return 1;
        
      if( __n != _n )
        __recurse(_n);

      var j:Int = __n % 2;
      var e:Int = Std.int((__n+2-j)/2);

      return (_k>=e) ? __row[_n-_k] :__row[_k];
    }

/**
* @description getRow( _n:Int ) - Return the n-th full row of Pascal's triangle
*
* @param _n:Int - Index of desired row (beginning at zero)
*
* @since 1.0
*
* @return Array:Full n-th row of Pascal's triangle
*
* Note: It is the caller's responsibility to delete the returned array if calling this method more than once
*
*/
    public function getRow(_n:Int):Array<Dynamic>  
    { 
      switch(_n)
      {
        case 0:
          return [1];
        
        case 1:
          return [1,1];
        
        case 2:
          return [1,2,1];
        
        default:
          var newRow:Array<Dynamic> = ( _n == __n ) ? __fillOut() :__recurse(_n);
          return newRow;
        }
    }

    // fill out nonsymmetric portion of current row, returning reference to full array
    function __fillOut():Array<Dynamic>
    {
      var j:Int    = __n % 2;
      var e:Int    = Std.int((__n+2-j)/2);
      var arr:Array<Dynamic> = __row.slice(0,e+1);

      if( j == 0 )
      {
        for( i in 0...e-1)
          arr[e+i] = arr[e-i-2];
      }
      else
      {
        for( i in 0...e)
          arr[e+i] = arr[e-i-1];
      }

      return arr;
    }

    // recursively generate desired row from the current row
    function __recurse(_r:Int):Array<Dynamic>
    {
      // forward or reverse?
      if( _r > __n )
        __forward(_r);
      else
      {
        // recurse backward or reset and move forward ... inquiring minds want to know :)
        if( (_r-2) <= (__n-_r) )
        {
          // reset and move forward
          __row[1] = 2;
          __n      = 2;
          __forward(_r);
        }
        else
          __reverse(_r);
      }

      __n = _r;
      return __fillOut(); 
    }

    // run recursion forward
    function __forward(_r:Int):Void
    {
      var i:Int=__n+1;
        // how many elements in the nonsymmetric portion of the current row?
       while ( i<=_r)
      {
        // how many elements in the nonsymmetric portion of the current row?
        var j:Int = i % 2;
        var e:Int = Std.int((i+2-j)/2);
        var h:Int = __row[0];
		var val:Int;
        if( j == 1 ) 
        { 
          for( k in 1...e)
          {
            val = __row[k] + h;
            h              = __row[k];
            __row[k]       = val;
          }
        }
        else
        {
          for( k in 1...e-1)
          {
            val      = __row[k] + h;
            h        = __row[k];
            __row[k] = val;
          }
          __row[e-1] = 2*h;
        }
      	++i ;
        // how many elements in the nonsymmetric portion of the current row?
       }
    }

    // run recursion backwards
    function __reverse(_r:Int):Void
    {
      var i:Int=__n-1;
        // how many elements in the nonsymmetric portion of the current row?
       while ( i>=_r)
      {
        // how many elements in the nonsymmetric portion of the current row?
        var j:Int = i % 2;
        var e:Int = Std.int((i+2-j)/2);
		var k:Int=1;
        //for(var k:Int=1;  k<e; ++k )
        while(k<e ){
			__row[k] = __row[k] - __row[k - 1];
			++k;
		}
      	i-- ;
        // how many elements in the nonsymmetric portion of the current row?
       }
    }
  }
